//给你一个字符串 s，找到 s 中最长的回文子串。
//
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
//
//
//
// 示例 1：
//
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//
// 示例 2：
//
//
//输入：s = "cbbd"
//输出："bb"
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由数字和英文字母组成
//
//
// Related Topics 字符串 动态规划 👍 6491 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
// ...,a,b,a,...
// ...,a,a,...
// 一趟遍历, 遇到回文串的"核"(我的发明的概念), "aba", "aa"
// 其实就是中心扩算法的思想, 但我的视线臃肿
class Solution5_1 {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        char[] chars = s.toCharArray();
        int N = chars.length;

        int[] ans = new int[2];
        for (int i = 0; i < N; i++) {
            char c = chars[i];

            {
                int l, r = i;
                int[] ans1 = new int[]{i, r};
                // 单核, 当前自身
                ans1[0] = l = i;
                for (l--, r++; r < N && l >= 0; l--, r++) {
                    if (chars[l] != chars[r]) {
                        break;
                    }
                }
                ans1 = new int[]{l + 1, r - 1};
                if (ans1[1] - ans1[0] > ans[1] - ans[0]) {
                    ans = ans1;
                }
            }

            if (i - 1 >= 0 && chars[i - 1] == c) {
                int l, r = i;
                int[] ans1 = new int[]{i, r};
                // 双核
                ans1[0] = l = i - 1;
                for (l--, r++; r < N && l >= 0; l--, r++) {
                    if (chars[l] != chars[r]) {
                        break;
                    }
                }
                ans1 = new int[]{l + 1, r - 1};
                if (ans1[1] - ans1[0] > ans[1] - ans[0]) {
                    ans = ans1;
                }
            }


        }

        int len = ans[1] - ans[0] + 1;
        return len == 0 ? "" : new String(chars, ans[0], len);
    }
}

// 暴力枚举起始位置 + 剪枝
class Solution5_2 {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        int ansSt = 0;
        int ansLen = 1; // 至少有一个

        char[] chars = s.toCharArray();
        int N = chars.length;

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                // 减枝
                int ansLen1 = j - i + 1;
                if (ansLen1 <= ansLen) {
                    // 已经有更长的, 没必要判断更短的
                    continue;
                }

                // i ~ j 是否是回文子串
                if (isValidPalindrome(chars, i, j)) {
                    ansSt = i;
                    ansLen = ansLen1;
                }
            }
        }

        return s.substring(ansSt, ansSt + ansLen);
    }

    private boolean isValidPalindrome(char[] chars, int left, int right) {
        while (left <= right && chars[left] == chars[right]) {
            left++;
            right--;
        }
        return left > right;
    }
}

// 自己憋出来的动规, 杂乱
class Solution5_3 {
    // 回文, 如果想象有一个镜像字符串, 就是找两个的最长公共子串 (有点类似最长公共子序列), 动规思路就接近了.
    // 考察 i 位置, 可能性
    // 打标记, 所有尝试中去最值
    public String longestPalindrome(String s) {
        int N = s.length();
        boolean[][] dp = new boolean[N][N];
        int[] ans = {0, 0}; // 至少会有一个
        for (int i = N - 1; i >= 0; i--) {
            for (int j = 0; j < N; j++) {
                if (i > j) {
                    dp[i][j] = true;
                    continue;
                }
                if (i == j) {
                    dp[i][j] = true;
                    if (j - i > ans[1] - ans[0]) {
                        ans = new int[]{i, j};
                    }
                    continue;
                }
                boolean ijEq = s.charAt(i) == s.charAt(j);
                if (j - 1 >= 0 && i + 1 < N && dp[i + 1][j - 1] && ijEq) {
                    dp[i][j] = true;
                    if (j - i > ans[1] - ans[0]) {
                        ans = new int[]{i, j};
                    }
                } else {
                    // i+1,j; i,j-1 如果是, 长度一样, 且更新过答案了
                    dp[i][j] = false;
                }
            }
        }

        int len = ans[1] - ans[0] + 1;
        return len > 0 ? s.substring(ans[0], ans[1] + 1) : "";
    }
}

// Solution5_3 简洁版
class Solution5_4
{
    public String longestPalindrome(String s) {
        int N = s.length();
        boolean[][] dp = new boolean[N][N];
        int[] ans = new int[]{0, 0};
        for (int i = N - 1; i >= 0; i--) {
            for (int j = N - 1; j >= 0; j--) {
                if (i > j) {
                    dp[i][j] = true;
                    continue;
                }
                if (i == j) {
                    dp[i][j] = true;
                    ans = ans[1] - ans[0] < j - i ? new int[]{i, j} : ans;
                    continue;
                }
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    ans = ans[1] - ans[0] < j - i ? new int[]{i, j} : ans;
                } else {
                    dp[i][j] = false;
                }
            }
        }

        return s.substring(ans[0], ans[1] + 1);
    }
}

// class Solution_250219 {
//
//     public String longestPalindrome(String s) {
//         // "\" 形对角线填充，中间往左下方向，dp[0][N] 为所求
//         // 只能得到最长回文串的长度，不能得到具体的串
//     }
// }

class Solution5_250219 {
// class Solution5 {
    public String longestPalindrome(String s) {
        // "\" 形对角线填充，中间往左下方向，dp[i][j] 是否为回文串, j-i+1 最大着即所求
        int N = s.length();
        boolean[][] dp = new boolean[N][N];
        int[] ans = new int[2];
        for (int k = 0; k < N; k++) {
            for (int i = 0, j = i + k; i < N && j < N; i++, j++) {
                if (j - i < 2) { // base case: 1 或 2 个字符
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                }
                else if (dp[i + 1][j - 1]) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                }
                if (dp[i][j] && j-i+1 > ans[1] - ans[0]) {
                    ans = new int[]{i, j + 1};
                }
            }
        }

        return s.substring(ans[0], ans[1]);
    }
}

// 执行耗时:143 ms,击败了28.35% 的Java用户
// 内存消耗:40.7 MB,击败了91.48% 的Java用户
class Solution5_S
{
    public String longestPalindrome(String s) {
        int N = s.length();
        boolean[] dp = new boolean[N];
        int[] ans = new int[]{0, 0}; // 至少是1
        for (int i = N - 1; i >= 0; i--) {
            for (int j = N - 1; j >= 0; j--) {
                if (i >= j) {
                    dp[j] = true;
                    continue;
                }

                if (s.charAt(i) == s.charAt(j) && dp[j - 1]) {
                    dp[j] = true;
                    ans = ans[1] - ans[0] < j - i ? new int[]{i, j} : ans;
                } else { // 此分支不可少, 因为是压缩数组, 需要消除上一轮 行 的影响
                    dp[j] = false;
                }
            }
        }

        return s.substring(ans[0], ans[1] + 1);
    }
}

//leetcode submit region end(Prohibit modification and deletion)

class Test5 {
    public static void main(String[] args) {
        // String res = new Solution().longestPalindrome("aacabdkacaa");
        // String res = new Solution().longestPalindrome("aaaa");
        // System.out.println(res);
        // String res = new Solution5_250219().longestPalindrome("aacabdkacaa");
        // String res = new Solution5_250219().longestPalindrome("aaaa");
        String res = new Solution5_250219().longestPalindrome("cbbd");
        System.out.println(res);
    }
}
